/*
 * @lc app=leetcode.cn id=64 lang=javascript
 *
 * [64] 最小路径和
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @return {number}
*/
// dp[0][x] = dp[0][x-1] + val 初始化
// dp[y][0] = dp[y - 1][0] + val 初始化
// dp[y][x] = min(dp[y-1][x],dp[x][y-1]) + val; y > 0 && x > 0
var minPathSum = function(grid) {
  let yl = grid.length
  let xl = grid[0].length
  let dp = Array.from({length: yl}, () => [])
  let yi = 1
  let xi = 1
  dp[0][0] = grid[0][0]
  while (yi < yl) {
    dp[yi][0] = dp[yi - 1][0] + grid[yi][0]
    yi++
  }
  while (xi < xl) {
    dp[0][xi] = dp[0][xi - 1] + grid[0][xi]
    xi++
  }
  for (let y = 1; y < yl; y++) {
    for (let x = 1; x < xl; x++) {
      dp[y][x] = Math.min(dp[y-1][x], dp[y][x-1]) + grid[y][x]
    }
  }
  return dp[yl-1][xl-1]
};
// @lc code=end

